A network is a group of two or more computer systems linked by wired or wireless connections. Data, commonly referred to as a packet, is transmitted from a source computer system at which the packet originates, to a destination computer system. Examples of sources and destinations include a desktop computer, a personal digital assistant, or a mobile or laptop computer. The computer systems in a network are commonly referred to as nodes.
A packet typically travels through intermediate computer systems during transmission. An example of an intermediate computer system is a switch or a router. In general, a router is a packet-forwarding device that receives a packet and determines a next node to which to forward the packet as it proceeds to its destination. In order to determine the next node, the router examines the packet's destination address, accesses the router's routing table, which includes routing table entries, and searches for a routing table entry (RTE) having a destination address that matches the packet's destination address. An RTE typically includes at least a destination, identified by a destination address; a mask length (discussed later, along with masks); a next node to which to forward the packet along the route to the destination; and some additional information.
An internetwork, e.g., the Internet, is the interconnection of many individual networks. The internet protocol (IP) is a protocol for routing packets on an internetwork, providing the set of rules for networks to communicate with each other. An IP address may identify a node, such as the packet's destination, a destination in a RTE, and/or a next node. An IP address typically includes decimal numbers are separated by periods. Each decimal number is commonly referred to as an octet. Each octet may be represented as a string of eight binary digits. For example, the IP address 148.225.3.61 includes four octets, and in binary form is 10010100.11100001.00000011.00111101. An octet is not limited to being represented as binary digits, e.g., an octet may be represented by two hexadecimal digits.
An IP address typically has two parts: a network number, which identifies the overall network of which a node is a part, and a node number, which identifies a specific node within the network. For example, in the destination address 148.225.3.61, the network number may be 148.225, and the node number 3.61. In IP version 4 (IPv4), an IP address includes four octets and is 32 bits in length, while in IP version 6 (IPv6), an IP address includes 16 octets and is 128 bits in length. See, e.g., Internet Engineering Task Force (IETF) Request for Comments (RFC) 1812, “Requirements for IP Version 4 Routers,” June 1995; IETF RFC 2460, “Internet Protocol, Version 6 (IPv6) Specification,” December 1998. There may be more than one RTE address that matches the packet's destination address, because one RTE may have the same network number as the destination address, while another entry may have the same network number and node number. In that case, the router typically selects, for determining the next node, the more specific RTE address that matches the destination address.
A mask is essentially a screen that indicates the bit positions in an address to examine. In a binary mask, a “1” in a bit position indicates that a bit occupying that bit position is a relevant bit, i.e., a bit to be examined, while a “0” indicates that the bit occupying that bit position is not a relevant bit, i.e., a bit not to be examined. In another type of mask, a hexadecimal mask, an “f” represents four relevant bits to examine, and a 0 indicates four irrelevant bits that are not to be examined. When a mask is applied to an address, a new address is generated based on the bits that are not relevant, that is, the relevant bits in the address remain unchanged, but the bits in the address that are not relevant are changed to 0s.
For example, a RTE may have a mask length of 16, represented by the mask 255.255.0.0 (11111111.11111111.00000000.00000000). The string of all 1s is an indication to examine, e.g., the network number, and the 0s indicate not to examine, e.g., the node number, possibly because the router is searching for another network to which to forward the packet (when the packet arrives at the other network, another router in that network may look at the whole address to determine the destination to which to forward the packet). A mask length reduces the need to examine a whole address, which allows for faster packet forwarding.
The combination of a destination address and a mask length is commonly referred to as a prefix. The prefix identifies the number of relevant bits used to identify a network. For example, 192.9.205.22/18 means the first 18 bits identify the network and the remaining 14 bits are used to identify hosts in the network. A prefix may be used to represent a RTE. A prefix that best matches a packet's destination address is commonly referred to as a longest prefix match, because such a prefix typically has more relevant bits that match the destination address, and thus a longer mask length, than a prefix whose address matches fewer relevant bits of the destination address. A search for a longest prefix match is commonly referred to as a longest prefix match search.
Longest prefix-match searching fits naturally into current destination address formatting (i.e., groups of decimal numbers separated by periods, where each decimal number represents a string of binary digits) and the destination-based hop-by-hop packet-forwarding paradigm. A routing table may be structured to facilitate longest prefix match searching. An example of a routing table structure that facilitates longest prefix match searching is a Patricia Tree, and the corresponding Patricia Tree algorithm is a technique used to determine a longest prefix match.
Generally, a traditional Patricia Tree consists of internal nodes and external nodes linked with one another. A node linked below another node is referred to as a child node of the node to which it is linked, while a node linked above another node is referred to as a parent node of the node to which it is linked. An external node typically identifies a prefix representing an RTE. An internal node specifies a bit position to examine, in order to determine the value of a bit occupying that bit position. The value of the bit determines the next node to which to proceed in the Patricia Tree, e.g., proceed to a left child node if the bit is a 0, or to a right child node if it is a 1. In a traditional Patricia Tree, an external node is a leaf node, meaning it has no child nodes, while an internal node is a non-leaf node, meaning it has at least one child node.
In a traditional Patricia Tree algorithm, a determination as to whether a prefix's address matches a packet's destination address occurs at an external node. This results in a disadvantage, commonly referred to as backtracking, of the Patricia Tree algorithm. Specifically, because a determination as to whether there is a match occurs at an external node, the algorithm backtracks up the Patricia Tree if there is no match, since the external nodes are leaf nodes. The algorithm applies a mask, thus changing irrelevant bits to 0s and altering the search if a bit that was changed to 0 occupies a bit position identified by an internal node, and repeats the search. When a router backtracks and repeats a search, routing table look-up speed is reduced, which slows router performance.